// Copyright (c) 2021, gottingen group.
// All rights reserved.
// Created by liyinbin lijippy@163.com

#ifndef ABEL_TRIE_HTRIE_HASH_H_
#define ABEL_TRIE_HTRIE_HASH_H_

#include <algorithm>
#include <array>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <iterator>
#include <limits>
#include <memory>
#include <stdexcept>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

#include "abel/trie/internal/array_map.h"
#include "abel/trie/internal/array_set.h"

/*
 * __has_include is a bit useless
 * (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79433), check also __cplusplus
 * version.
 */
#ifdef __has_include
#if __has_include(<string_view>) && __cplusplus >= 201703L
#define TSL_HT_HAS_STRING_VIEW
#endif
#endif

#ifdef TSL_HT_HAS_STRING_VIEW

#include <string_view>

#endif

#ifdef TSL_DEBUG
#define tsl_ht_assert(expr) assert(expr)
#else
#define tsl_ht_assert(expr) (static_cast<void>(0))
#endif

namespace abel {

namespace detail_htrie_hash {

template<typename T, typename = void>
struct is_iterator : std::false_type {
};

template<typename T>
struct is_iterator<T, typename std::enable_if<!std::is_same<
        typename std::iterator_traits<T>::iterator_category,
        void>::value>::type> : std::true_type {
};

template<typename T, typename... U>
struct is_related : std::false_type {
};

template<typename T, typename U>
struct is_related<T, U>
        : std::is_same<typename std::remove_cv<
                typename std::remove_reference<T>::type>::type,
                typename std::remove_cv<
                        typename std::remove_reference<U>::type>::type> {
};

template<typename T, typename U>
static T numeric_cast(U value,
                      const char *error_message = "numeric_cast() failed.") {
    T ret = static_cast<T>(value);
    if (static_cast<U>(ret) != value) {
        throw std::runtime_error(error_message);
    }

    const bool is_same_signedness =
            (std::is_unsigned<T>::value && std::is_unsigned<U>::value) ||
            (std::is_signed<T>::value && std::is_signed<U>::value);
    if (!is_same_signedness && (ret < T{}) != (value < U{})) {
        throw std::runtime_error(error_message);
    }

    return ret;
}

template<class T>
struct value_node {
    /*
     * Avoid conflict with copy constructor 'value_node(const value_node&)'. If we
     * call the copy constructor with a mutable reference
     * 'value_node(value_node&)', we don't want the forward constructor to be
     * called.
     */
    template<class... Args, typename std::enable_if<!is_related<
            value_node, Args...>::value>::type * = nullptr>
    value_node(Args &&... args) : m_value(std::forward<Args>(args)...) {}

    T m_value;
};

template<>
struct value_node<void> {
};

/**
 * T should be void if there is no value associated to a key (in a set for
 * example).
 */
template<class CharT, class T, class Hash, class KeySizeT>
class htrie_hash {
  private:
    template<typename U>
    using has_value =
    typename std::integral_constant<bool, !std::is_same<U, void>::value>;

    static_assert(std::is_same<CharT, char>::value,
                  "char is the only supported CharT type for now.");

    static const std::size_t ALPHABET_SIZE =
            std::numeric_limits<typename std::make_unsigned<CharT>::type>::max() + 1;

  public:
    template<bool IsConst, bool IsPrefixIterator>
    class htrie_hash_iterator;

    using char_type = CharT;
    using key_size_type = KeySizeT;
    using size_type = std::size_t;
    using hasher = Hash;
    using iterator = htrie_hash_iterator<false, false>;
    using const_iterator = htrie_hash_iterator<true, false>;
    using prefix_iterator = htrie_hash_iterator<false, true>;
    using const_prefix_iterator = htrie_hash_iterator<true, true>;

  private:
    using array_hash_type = typename std::conditional<
            has_value<T>::value,
            abel::array_map<CharT, T, Hash, abel::trie_internal::str_equal<CharT>, false, KeySizeT,
                    std::uint16_t, abel::trie_internal::power_of_two_growth_policy<4>>,
            abel::array_set<CharT, Hash, abel::trie_internal::str_equal<CharT>, false, KeySizeT,
                    std::uint16_t,
                    abel::trie_internal::power_of_two_growth_policy<4>>>::type;

  private:
    /*
     * The tree is mainly composed of two nodes types: trie_node and hash_node
     * which both have anode as base class. Each child is either a hash_node or a
     * trie_node.
     *
     * A hash_node is always a leaf node, it doesn't have any child.
     *
     * Example:
     *      | ... | a |.. ..................... | f | ... | trie_node_1
     *               \                             \
     * hash_node_1 |array_hash = {"dd"}|     |...| a | ... | trie_node_2
     *                                             /
     *                     |array_hash = {"ble", "bric", "lse"}| hash_node_2
     *
     *
     * Each trie_node may also have a value node, which contains a value T, if the
     * trie_node marks the end of a string value.
     *
     * A trie node should at least have one child or a value node. There can't be
     * a trie node without any child and no value node.
     */

    using value_node = abel::detail_htrie_hash::value_node<T>;

    class trie_node;

    class hash_node;

    // TODO better encapsulate operations modifying the tree.
    class anode {
        friend class trie_node;

      public:
        /*
         * TODO Avoid the virtual to economize 8 bytes. We could use a custom
         * deleter in the std::unique_ptr<anode> we use (as we know if an anode is a
         * trie_node or hash_node).
         */
        virtual ~anode() = default;

        bool is_trie_node() const noexcept {
            return m_node_type == node_type::TRIE_NODE;
        }

        bool is_hash_node() const noexcept {
            return m_node_type == node_type::HASH_NODE;
        }

        trie_node &as_trie_node() noexcept {
            tsl_ht_assert(is_trie_node());
            return static_cast<trie_node &>(*this);
        }

        hash_node &as_hash_node() noexcept {
            tsl_ht_assert(is_hash_node());
            return static_cast<hash_node &>(*this);
        }

        const trie_node &as_trie_node() const noexcept {
            tsl_ht_assert(is_trie_node());
            return static_cast<const trie_node &>(*this);
        }

        const hash_node &as_hash_node() const noexcept {
            tsl_ht_assert(is_hash_node());
            return static_cast<const hash_node &>(*this);
        }

        /**
         * @see m_child_of_char
         */
        CharT child_of_char() const noexcept {
            tsl_ht_assert(parent() != nullptr);
            return m_child_of_char;
        }

        /**
         * Return nullptr if none.
         */
        trie_node *parent() noexcept { return m_parent_node; }

        const trie_node *parent() const noexcept { return m_parent_node; }

      protected:
        enum class node_type : unsigned char {
            HASH_NODE, TRIE_NODE
        };

        anode(node_type node_type_)
                : m_node_type(node_type_), m_child_of_char(0), m_parent_node(nullptr) {}

        anode(node_type node_type_, CharT child_of_char)
                : m_node_type(node_type_),
                  m_child_of_char(child_of_char),
                  m_parent_node(nullptr) {}

      protected:
        node_type m_node_type;

        /**
         * If the node has a parent, then it's a descendant of some char.
         *
         * Example:
         *      | ... | a | b | ... | trie_node_1
         *                   \
         *              |...| a | ... | trie_node_2
         *                   /
         *            |array_hash| hash_node_1
         *
         * trie_node_2 is a child of trie_node_1 through 'b', it will have 'b' as
         * m_child_of_char. hash_node_1 is a child of trie_node_2 through 'a', it
         * will have 'a' as m_child_of_char.
         *
         * trie_node_1 has no parent, its m_child_of_char is undefined.
         */
        CharT m_child_of_char;
        trie_node *m_parent_node;
    };

    // Give the position in trie_node::m_children corresponding to the character c
    static std::size_t as_position(CharT c) noexcept {
        return static_cast<std::size_t>(
                static_cast<typename std::make_unsigned<CharT>::type>(c));
    }

    class trie_node : public anode {
      public:
        trie_node()
                : anode(anode::node_type::TRIE_NODE),
                  m_value_node(nullptr),
                  m_children() {}

        trie_node(const trie_node &other)
                : anode(anode::node_type::TRIE_NODE, other.m_child_of_char),
                  m_value_node(nullptr),
                  m_children() {
            if (other.m_value_node != nullptr) {
                m_value_node = make_unique<value_node>(*other.m_value_node);
            }

            // TODO avoid recursion
            for (std::size_t ichild = 0; ichild < other.m_children.size(); ichild++) {
                if (other.m_children[ichild] != nullptr) {
                    if (other.m_children[ichild]->is_hash_node()) {
                        m_children[ichild] = make_unique<hash_node>(
                                other.m_children[ichild]->as_hash_node());
                    } else {
                        m_children[ichild] = make_unique<trie_node>(
                                other.m_children[ichild]->as_trie_node());
                    }

                    m_children[ichild]->m_parent_node = this;
                }
            }
        }

        trie_node(trie_node &&other) = delete;

        trie_node &operator=(const trie_node &other) = delete;

        trie_node &operator=(trie_node &&other) = delete;

        /**
         * Return nullptr if none.
         */
        anode *first_child() noexcept {
            return const_cast<anode *>(
                    static_cast<const trie_node *>(this)->first_child());
        }

        const anode *first_child() const noexcept {
            for (std::size_t ichild = 0; ichild < m_children.size(); ichild++) {
                if (m_children[ichild] != nullptr) {
                    return m_children[ichild].get();
                }
            }

            return nullptr;
        }

        /**
         * Get the next_child that come after current_child. Return nullptr if no
         * next child.
         */
        anode *next_child(const anode &current_child) noexcept {
            return const_cast<anode *>(
                    static_cast<const trie_node *>(this)->next_child(current_child));
        }

        const anode *next_child(const anode &current_child) const noexcept {
            tsl_ht_assert(current_child.parent() == this);

            for (std::size_t ichild = as_position(current_child.child_of_char()) + 1;
                 ichild < m_children.size(); ichild++) {
                if (m_children[ichild] != nullptr) {
                    return m_children[ichild].get();
                }
            }

            return nullptr;
        }

        /**
         * Return the first left-descendant trie node with an m_value_node. If none
         * return the most left trie node.
         */
        trie_node &most_left_descendant_value_trie_node() noexcept {
            return const_cast<trie_node &>(
                    static_cast<const trie_node *>(this)
                            ->most_left_descendant_value_trie_node());
        }

        const trie_node &most_left_descendant_value_trie_node() const noexcept {
            const trie_node *current_node = this;
            while (true) {
                if (current_node->m_value_node != nullptr) {
                    return *current_node;
                }

                const anode *first_child = current_node->first_child();
                tsl_ht_assert(first_child !=
                              nullptr);  // a trie_node must either have a value_node or
                // at least one child.
                if (first_child->is_hash_node()) {
                    return *current_node;
                }

                current_node = &first_child->as_trie_node();
            }
        }

        size_type nb_children() const noexcept {
            return std::count_if(
                    m_children.cbegin(), m_children.cend(),
                    [](const std::unique_ptr<anode> &n) { return n != nullptr; });
        }

        bool empty() const noexcept {
            return std::all_of(
                    m_children.cbegin(), m_children.cend(),
                    [](const std::unique_ptr<anode> &n) { return n == nullptr; });
        }

        std::unique_ptr<anode> &child(CharT for_char) noexcept {
            return m_children[as_position(for_char)];
        }

        const std::unique_ptr<anode> &child(CharT for_char) const noexcept {
            return m_children[as_position(for_char)];
        }

        typename std::array<std::unique_ptr<anode>, ALPHABET_SIZE>::iterator
        begin() noexcept {
            return m_children.begin();
        }

        typename std::array<std::unique_ptr<anode>, ALPHABET_SIZE>::iterator
        end() noexcept {
            return m_children.end();
        }

        void set_child(CharT for_char, std::unique_ptr<anode> child) noexcept {
            if (child != nullptr) {
                child->m_child_of_char = for_char;
                child->m_parent_node = this;
            }

            m_children[as_position(for_char)] = std::move(child);
        }

        std::unique_ptr<value_node> &val_node() noexcept { return m_value_node; }

        const std::unique_ptr<value_node> &val_node() const noexcept {
            return m_value_node;
        }

      private:
        // TODO Avoid storing a value_node when has_value<T>::value is false
        std::unique_ptr<value_node> m_value_node;

        /**
         * Each character CharT corresponds to one position in the array. To convert
         * a character to a position use the as_position method.
         *
         * TODO Try to reduce the size of m_children with a hash map, linear/binary
         * search on array, ...
         * TODO Store number of non-null values in m_children. Check if we can store
         * this value in the alignment space as we don't want the node to get bigger
         * (empty() and nb_children() are rarely used so it is not an important
         * variable).
         */
        std::array<std::unique_ptr<anode>, ALPHABET_SIZE> m_children;
    };

    class hash_node : public anode {
      public:
        hash_node(const Hash &hash, float max_load_factor)
                : hash_node(HASH_NODE_DEFAULT_INIT_BUCKETS_COUNT, hash,
                            max_load_factor) {}

        hash_node(size_type bucket_count, const Hash &hash, float max_load_factor)
                : anode(anode::node_type::HASH_NODE), m_array_hash(bucket_count, hash) {
            m_array_hash.max_load_factor(max_load_factor);
        }

        hash_node(array_hash_type &&array_hash) noexcept(
        std::is_nothrow_move_constructible<array_hash_type>::value)
                : anode(anode::node_type::HASH_NODE),
                  m_array_hash(std::move(array_hash)) {}

        hash_node(const hash_node &other) = default;

        hash_node(hash_node &&other) = delete;

        hash_node &operator=(const hash_node &other) = delete;

        hash_node &operator=(hash_node &&other) = delete;

        array_hash_type &array_hash() noexcept { return m_array_hash; }

        const array_hash_type &array_hash() const noexcept { return m_array_hash; }

      private:
        array_hash_type m_array_hash;
    };

  public:
    template<bool IsConst, bool IsPrefixIterator>
    class htrie_hash_iterator {
        friend class htrie_hash;

      private:
        using anode_type =
        typename std::conditional<IsConst, const anode, anode>::type;
        using trie_node_type =
        typename std::conditional<IsConst, const trie_node, trie_node>::type;
        using hash_node_type =
        typename std::conditional<IsConst, const hash_node, hash_node>::type;

        using array_hash_iterator_type =
        typename std::conditional<IsConst,
                typename array_hash_type::const_iterator,
                typename array_hash_type::iterator>::type;

      public:
        using iterator_category = std::forward_iterator_tag;
        using value_type =
        typename std::conditional<has_value<T>::value, T, void>::type;
        using difference_type = std::ptrdiff_t;
        using reference = typename std::conditional<
                has_value<T>::value,
                typename std::conditional<
                        IsConst, typename std::add_lvalue_reference<const T>::type,
                        typename std::add_lvalue_reference<T>::type>::type,
                void>::type;
        using pointer = typename std::conditional<
                has_value<T>::value,
                typename std::conditional<IsConst, const T *, T *>::type, void>::type;

      private:
        /**
         * Start reading from start_hash_node->array_hash().begin().
         */
        htrie_hash_iterator(hash_node_type &start_hash_node) noexcept
                : htrie_hash_iterator(start_hash_node,
                                      start_hash_node.array_hash().begin()) {}

        /**
         * Start reading from iterator begin in start_hash_node->array_hash().
         */
        htrie_hash_iterator(hash_node_type &start_hash_node,
                            array_hash_iterator_type begin) noexcept
                : m_current_trie_node(start_hash_node.parent()),
                  m_current_hash_node(&start_hash_node),
                  m_array_hash_iterator(begin),
                  m_array_hash_end_iterator(start_hash_node.array_hash().end()),
                  m_read_trie_node_value(false) {
            tsl_ht_assert(!m_current_hash_node->array_hash().empty());
        }

        /**
         * Start reading from the value in start_trie_node.
         * start_trie_node->val_node() should be non-null.
         */
        htrie_hash_iterator(trie_node_type &start_trie_node) noexcept
                : m_current_trie_node(&start_trie_node),
                  m_current_hash_node(nullptr),
                  m_read_trie_node_value(true) {
            tsl_ht_assert(m_current_trie_node->val_node() != nullptr);
        }

        template<bool P = IsPrefixIterator,
                typename std::enable_if<!P>::type * = nullptr>
        htrie_hash_iterator(trie_node_type *tnode, hash_node_type *hnode,
                            array_hash_iterator_type begin,
                            array_hash_iterator_type end,
                            bool read_trie_node_value) noexcept
                : m_current_trie_node(tnode),
                  m_current_hash_node(hnode),
                  m_array_hash_iterator(begin),
                  m_array_hash_end_iterator(end),
                  m_read_trie_node_value(read_trie_node_value) {}

        template<bool P = IsPrefixIterator,
                typename std::enable_if<P>::type * = nullptr>
        htrie_hash_iterator(trie_node_type *tnode, hash_node_type *hnode,
                            array_hash_iterator_type begin,
                            array_hash_iterator_type end, bool read_trie_node_value,
                            std::basic_string<CharT> prefix_filter) noexcept
                : m_current_trie_node(tnode),
                  m_current_hash_node(hnode),
                  m_array_hash_iterator(begin),
                  m_array_hash_end_iterator(end),
                  m_read_trie_node_value(read_trie_node_value),
                  m_prefix_filter(std::move(prefix_filter)) {}

      public:
        htrie_hash_iterator() noexcept {}

        // Copy constructor from iterator to const_iterator.
        template<bool TIsConst = IsConst,
                bool TIsPrefixIterator = IsPrefixIterator,
                typename std::enable_if<TIsConst && !TIsPrefixIterator>::type * =
                nullptr>
        htrie_hash_iterator(
                const htrie_hash_iterator<!TIsConst, TIsPrefixIterator> &other) noexcept
                : m_current_trie_node(other.m_current_trie_node),
                  m_current_hash_node(other.m_current_hash_node),
                  m_array_hash_iterator(other.m_array_hash_iterator),
                  m_array_hash_end_iterator(other.m_array_hash_end_iterator),
                  m_read_trie_node_value(other.m_read_trie_node_value) {}

        // Copy constructor from iterator to const_iterator.
        template<
                bool TIsConst = IsConst, bool TIsPrefixIterator = IsPrefixIterator,
                typename std::enable_if<TIsConst && TIsPrefixIterator>::type * = nullptr>
        htrie_hash_iterator(
                const htrie_hash_iterator<!TIsConst, TIsPrefixIterator> &other) noexcept
                : m_current_trie_node(other.m_current_trie_node),
                  m_current_hash_node(other.m_current_hash_node),
                  m_array_hash_iterator(other.m_array_hash_iterator),
                  m_array_hash_end_iterator(other.m_array_hash_end_iterator),
                  m_read_trie_node_value(other.m_read_trie_node_value),
                  m_prefix_filter(other.m_prefix_filter) {}

        htrie_hash_iterator(const htrie_hash_iterator &other) = default;

        htrie_hash_iterator(htrie_hash_iterator &&other) = default;

        htrie_hash_iterator &operator=(const htrie_hash_iterator &other) = default;

        htrie_hash_iterator &operator=(htrie_hash_iterator &&other) = default;

        void key(std::basic_string<CharT> &key_buffer_out) const {
            key_buffer_out.clear();

            trie_node_type *tnode = m_current_trie_node;
            while (tnode != nullptr && tnode->parent() != nullptr) {
                key_buffer_out.push_back(tnode->child_of_char());
                tnode = tnode->parent();
            }

            std::reverse(key_buffer_out.begin(), key_buffer_out.end());

            if (!m_read_trie_node_value) {
                tsl_ht_assert(m_current_hash_node != nullptr);
                if (m_current_hash_node->parent() != nullptr) {
                    key_buffer_out.push_back(m_current_hash_node->child_of_char());
                }

                key_buffer_out.append(m_array_hash_iterator.key(),
                                      m_array_hash_iterator.key_size());
            }
        }

        std::basic_string<CharT> key() const {
            std::basic_string<CharT> key_buffer;
            key(key_buffer);

            return key_buffer;
        }

        template<class U = T,
                typename std::enable_if<has_value<U>::value>::type * = nullptr>
        reference value() const {
            if (this->m_read_trie_node_value) {
                tsl_ht_assert(this->m_current_trie_node != nullptr);
                tsl_ht_assert(this->m_current_trie_node->val_node() != nullptr);

                return this->m_current_trie_node->val_node()->m_value;
            } else {
                return this->m_array_hash_iterator.value();
            }
        }

        template<class U = T,
                typename std::enable_if<has_value<U>::value>::type * = nullptr>
        reference operator*() const {
            return value();
        }

        template<class U = T,
                typename std::enable_if<has_value<U>::value>::type * = nullptr>
        pointer operator->() const {
            return std::addressof(value());
        }

        htrie_hash_iterator &operator++() {
            if (m_read_trie_node_value) {
                tsl_ht_assert(m_current_trie_node != nullptr);

                m_read_trie_node_value = false;

                anode_type *child = m_current_trie_node->first_child();
                if (child != nullptr) {
                    set_most_left_descendant_as_next_node(*child);
                } else if (m_current_trie_node->parent() != nullptr) {
                    trie_node_type *current_node_child = m_current_trie_node;
                    m_current_trie_node = m_current_trie_node->parent();

                    set_next_node_ascending(*current_node_child);
                } else {
                    set_as_end_iterator();
                }
            } else {
                ++m_array_hash_iterator;
                if (m_array_hash_iterator != m_array_hash_end_iterator) {
                    filter_prefix();
                }
                    // End of the road, set the iterator as an end node.
                else if (m_current_trie_node == nullptr) {
                    set_as_end_iterator();
                } else {
                    tsl_ht_assert(m_current_hash_node != nullptr);
                    set_next_node_ascending(*m_current_hash_node);
                }
            }

            return *this;
        }

        htrie_hash_iterator operator++(int) {
            htrie_hash_iterator tmp(*this);
            ++*this;

            return tmp;
        }

        friend bool operator==(const htrie_hash_iterator &lhs,
                               const htrie_hash_iterator &rhs) {
            if (lhs.m_current_trie_node != rhs.m_current_trie_node ||
                lhs.m_read_trie_node_value != rhs.m_read_trie_node_value) {
                return false;
            } else if (lhs.m_read_trie_node_value) {
                return true;
            } else {
                if (lhs.m_current_hash_node != rhs.m_current_hash_node) {
                    return false;
                } else if (lhs.m_current_hash_node == nullptr) {
                    return true;
                } else {
                    return lhs.m_array_hash_iterator == rhs.m_array_hash_iterator &&
                           lhs.m_array_hash_end_iterator == rhs.m_array_hash_end_iterator;
                }
            }
        }

        friend bool operator!=(const htrie_hash_iterator &lhs,
                               const htrie_hash_iterator &rhs) {
            return !(lhs == rhs);
        }

      private:
        void hash_node_prefix(std::basic_string<CharT> &key_buffer_out) const {
            tsl_ht_assert(!m_read_trie_node_value);
            key_buffer_out.clear();

            trie_node_type *tnode = m_current_trie_node;
            while (tnode != nullptr && tnode->parent() != nullptr) {
                key_buffer_out.push_back(tnode->child_of_char());
                tnode = tnode->parent();
            }

            std::reverse(key_buffer_out.begin(), key_buffer_out.end());

            tsl_ht_assert(m_current_hash_node != nullptr);
            if (m_current_hash_node->parent() != nullptr) {
                key_buffer_out.push_back(m_current_hash_node->child_of_char());
            }
        }

        template<bool P = IsPrefixIterator,
                typename std::enable_if<!P>::type * = nullptr>
        void filter_prefix() {}

        template<bool P = IsPrefixIterator,
                typename std::enable_if<P>::type * = nullptr>
        void filter_prefix() {
            tsl_ht_assert(m_array_hash_iterator != m_array_hash_end_iterator);
            tsl_ht_assert(!m_read_trie_node_value && m_current_hash_node != nullptr);

            if (m_prefix_filter.empty()) {
                return;
            }

            while ((m_prefix_filter.size() > m_array_hash_iterator.key_size() ||
                    m_prefix_filter.compare(0, m_prefix_filter.size(),
                                            m_array_hash_iterator.key(),
                                            m_prefix_filter.size()) != 0)) {
                ++m_array_hash_iterator;
                if (m_array_hash_iterator == m_array_hash_end_iterator) {
                    if (m_current_trie_node == nullptr) {
                        set_as_end_iterator();
                    } else {
                        tsl_ht_assert(m_current_hash_node != nullptr);
                        set_next_node_ascending(*m_current_hash_node);
                    }

                    return;
                }
            }
        }

        /**
         * Go back up in the tree to get the current_trie_node_child sibling.
         * If none, try to go back up more in the tree to check the siblings of the
         * ancestors.
         */
        void set_next_node_ascending(anode_type &current_trie_node_child) {
            tsl_ht_assert(m_current_trie_node != nullptr);
            tsl_ht_assert(current_trie_node_child.parent() == m_current_trie_node);

            anode_type *next_node =
                    m_current_trie_node->next_child(current_trie_node_child);
            while (next_node == nullptr && m_current_trie_node->parent() != nullptr) {
                anode_type *current_child = m_current_trie_node;
                m_current_trie_node = m_current_trie_node->parent();
                next_node = m_current_trie_node->next_child(*current_child);
            }

            // End of the road, set the iterator as an end node.
            if (next_node == nullptr) {
                set_as_end_iterator();
            } else {
                set_most_left_descendant_as_next_node(*next_node);
            }
        }

        void set_most_left_descendant_as_next_node(anode_type &search_start) {
            if (search_start.is_hash_node()) {
                set_current_hash_node(search_start.as_hash_node());
            } else {
                m_current_trie_node =
                        &search_start.as_trie_node().most_left_descendant_value_trie_node();
                if (m_current_trie_node->val_node() != nullptr) {
                    m_read_trie_node_value = true;
                } else {
                    anode_type *first_child = m_current_trie_node->first_child();
                    // a trie_node must either have a value_node or at least one child.
                    tsl_ht_assert(first_child != nullptr);

                    set_current_hash_node(first_child->as_hash_node());
                }
            }
        }

        void set_current_hash_node(hash_node_type &hnode) {
            tsl_ht_assert(!hnode.array_hash().empty());

            m_current_hash_node = &hnode;
            m_array_hash_iterator = m_current_hash_node->array_hash().begin();
            m_array_hash_end_iterator = m_current_hash_node->array_hash().end();
        }

        void set_as_end_iterator() {
            m_current_trie_node = nullptr;
            m_current_hash_node = nullptr;
            m_read_trie_node_value = false;
        }

        void skip_hash_node() {
            tsl_ht_assert(!m_read_trie_node_value && m_current_hash_node != nullptr);
            if (m_current_trie_node == nullptr) {
                set_as_end_iterator();
            } else {
                tsl_ht_assert(m_current_hash_node != nullptr);
                set_next_node_ascending(*m_current_hash_node);
            }
        }

      private:
        trie_node_type *m_current_trie_node;
        hash_node_type *m_current_hash_node;

        array_hash_iterator_type m_array_hash_iterator;
        array_hash_iterator_type m_array_hash_end_iterator;

        bool m_read_trie_node_value;
        // TODO can't have void if !IsPrefixIterator, use inheritance
        typename std::conditional<IsPrefixIterator, std::basic_string<CharT>,
                bool>::type m_prefix_filter;
    };

  public:
    htrie_hash(const Hash &hash, float max_load_factor, size_type burst_threshold)
            : m_root(nullptr),
              m_nb_elements(0),
              m_hash(hash),
              m_max_load_factor(max_load_factor) {
        this->burst_threshold(burst_threshold);
    }

    htrie_hash(const htrie_hash &other)
            : m_root(nullptr),
              m_nb_elements(other.m_nb_elements),
              m_hash(other.m_hash),
              m_max_load_factor(other.m_max_load_factor),
              m_burst_threshold(other.m_burst_threshold) {
        if (other.m_root != nullptr) {
            if (other.m_root->is_hash_node()) {
                m_root = make_unique<hash_node>(other.m_root->as_hash_node());
            } else {
                m_root = make_unique<trie_node>(other.m_root->as_trie_node());
            }
        }
    }

    htrie_hash(htrie_hash &&other) noexcept(
    std::is_nothrow_move_constructible<Hash>::value)
            : m_root(std::move(other.m_root)),
              m_nb_elements(other.m_nb_elements),
              m_hash(std::move(other.m_hash)),
              m_max_load_factor(other.m_max_load_factor),
              m_burst_threshold(other.m_burst_threshold) {
        other.clear();
    }

    htrie_hash &operator=(const htrie_hash &other) {
        if (&other != this) {
            std::unique_ptr<anode> new_root = nullptr;
            if (other.m_root != nullptr) {
                if (other.m_root->is_hash_node()) {
                    new_root = make_unique<hash_node>(other.m_root->as_hash_node());
                } else {
                    new_root = make_unique<trie_node>(other.m_root->as_trie_node());
                }
            }

            m_hash = other.m_hash;
            m_root = std::move(new_root);
            m_nb_elements = other.m_nb_elements;
            m_max_load_factor = other.m_max_load_factor;
            m_burst_threshold = other.m_burst_threshold;
        }

        return *this;
    }

    htrie_hash &operator=(htrie_hash &&other) {
        other.swap(*this);
        other.clear();

        return *this;
    }

    /*
     * Iterators
     */
    iterator begin() noexcept { return mutable_iterator(cbegin()); }

    const_iterator begin() const noexcept { return cbegin(); }

    const_iterator cbegin() const noexcept {
        if (empty()) {
            return cend();
        }

        return cbegin < const_iterator > (*m_root);
    }

    iterator end() noexcept {
        iterator it;
        it.set_as_end_iterator();

        return it;
    }

    const_iterator end() const noexcept { return cend(); }

    const_iterator cend() const noexcept {
        const_iterator it;
        it.set_as_end_iterator();

        return it;
    }

    /*
     * Capacity
     */
    bool empty() const noexcept { return m_nb_elements == 0; }

    size_type size() const noexcept { return m_nb_elements; }

    size_type max_size() const noexcept {
        return std::numeric_limits<size_type>::max();
    }

    size_type max_key_size() const noexcept {
        return array_hash_type::MAX_KEY_SIZE;
    }

    void shrink_to_fit() {
        auto first = begin();
        auto last = end();

        while (first != last) {
            if (first.m_read_trie_node_value) {
                ++first;
            } else {
                /*
                 * shrink_to_fit on array_hash will invalidate the iterators of
                 * array_hash. Save pointer to array_hash, skip the array_hash_node and
                 * then call shrink_to_fit on the saved pointer.
                 */
                hash_node *hnode = first.m_current_hash_node;
                first.skip_hash_node();

                tsl_ht_assert(hnode != nullptr);
                hnode->array_hash().shrink_to_fit();
            }
        }
    }

    /*
     * Modifiers
     */
    void clear() noexcept {
        m_root.reset(nullptr);
        m_nb_elements = 0;
    }

    template<class... ValueArgs>
    std::pair<iterator, bool> insert(const CharT *key, size_type key_size,
                                     ValueArgs &&... value_args) {
        if (key_size > max_key_size()) {
            throw std::length_error("Key is too long.");
        }

        if (m_root == nullptr) {
            m_root = make_unique<hash_node>(m_hash, m_max_load_factor);
        }

        return insert_impl(*m_root, key, key_size,
                           std::forward<ValueArgs>(value_args)...);
    }

    iterator erase(const_iterator pos) { return erase(mutable_iterator(pos)); }

    iterator erase(const_iterator first, const_iterator last) {
        // TODO Optimize, could avoid the call to std::distance
        const std::size_t nb_to_erase = std::size_t(std::distance(first, last));
        auto to_delete = mutable_iterator(first);
        for (std::size_t i = 0; i < nb_to_erase; i++) {
            to_delete = erase(to_delete);
        }

        return to_delete;
    }

    size_type erase(const CharT *key, size_type key_size) {
        auto it = find(key, key_size);
        if (it != end()) {
            erase(it);
            return 1;
        } else {
            return 0;
        }
    }

    size_type erase_prefix(const CharT *prefix, size_type prefix_size) {
        if (m_root == nullptr) {
            return 0;
        }

        anode *current_node = m_root.get();
        for (size_type iprefix = 0; iprefix < prefix_size; iprefix++) {
            if (current_node->is_trie_node()) {
                trie_node *tnode = &current_node->as_trie_node();

                if (tnode->child(prefix[iprefix]) == nullptr) {
                    return 0;
                } else {
                    current_node = tnode->child(prefix[iprefix]).get();
                }
            } else {
                hash_node &hnode = current_node->as_hash_node();
                return erase_prefix_hash_node(hnode, prefix + iprefix,
                                              prefix_size - iprefix);
            }
        }

        if (current_node->is_trie_node()) {
            trie_node *parent = current_node->parent();

            if (parent != nullptr) {
                const size_type nb_erased =
                        size_descendants(current_node->as_trie_node());

                parent->set_child(current_node->child_of_char(), nullptr);
                m_nb_elements -= nb_erased;

                if (parent->empty()) {
                    clear_empty_nodes(*parent);
                }

                return nb_erased;
            } else {
                const size_type nb_erased = m_nb_elements;
                m_root.reset(nullptr);
                m_nb_elements = 0;

                return nb_erased;
            }
        } else {
            const size_type nb_erased =
                    current_node->as_hash_node().array_hash().size();

            current_node->as_hash_node().array_hash().clear();
            m_nb_elements -= nb_erased;

            clear_empty_nodes(current_node->as_hash_node());

            return nb_erased;
        }
    }

    void swap(htrie_hash &other) {
        using std::swap;

        swap(m_hash, other.m_hash);
        swap(m_root, other.m_root);
        swap(m_nb_elements, other.m_nb_elements);
        swap(m_max_load_factor, other.m_max_load_factor);
        swap(m_burst_threshold, other.m_burst_threshold);
    }

    /*
     * Lookup
     */
    template<class U = T,
            typename std::enable_if<has_value<U>::value>::type * = nullptr>
    U &at(const CharT *key, size_type key_size) {
        return const_cast<U &>(
                static_cast<const htrie_hash *>(this)->at(key, key_size));
    }

    template<class U = T,
            typename std::enable_if<has_value<U>::value>::type * = nullptr>
    const U &at(const CharT *key, size_type key_size) const {
        auto it_find = find(key, key_size);
        if (it_find != cend()) {
            return it_find.value();
        } else {
            throw std::out_of_range("Couldn't find key.");
        }
    }

    // TODO optimize
    template<class U = T,
            typename std::enable_if<has_value<U>::value>::type * = nullptr>
    U &access_operator(const CharT *key, size_type key_size) {
        auto it_find = find(key, key_size);
        if (it_find != cend()) {
            return it_find.value();
        } else {
            return insert(key, key_size, U{}).first.value();
        }
    }

    size_type count(const CharT *key, size_type key_size) const {
        if (find(key, key_size) != cend()) {
            return 1;
        } else {
            return 0;
        }
    }

    iterator find(const CharT *key, size_type key_size) {
        if (m_root == nullptr) {
            return end();
        }

        return find_impl(*m_root, key, key_size);
    }

    const_iterator find(const CharT *key, size_type key_size) const {
        if (m_root == nullptr) {
            return cend();
        }

        return find_impl(*m_root, key, key_size);
    }

    std::pair<iterator, iterator> equal_range(const CharT *key,
                                              size_type key_size) {
        iterator it = find(key, key_size);
        return std::make_pair(it, (it == end()) ? it : std::next(it));
    }

    std::pair<const_iterator, const_iterator> equal_range(
            const CharT *key, size_type key_size) const {
        const_iterator it = find(key, key_size);
        return std::make_pair(it, (it == cend()) ? it : std::next(it));
    }

    std::pair<prefix_iterator, prefix_iterator> equal_prefix_range(
            const CharT *prefix, size_type prefix_size) {
        if (m_root == nullptr) {
            return std::make_pair(prefix_end(), prefix_end());
        }

        return equal_prefix_range_impl(*m_root, prefix, prefix_size);
    }

    std::pair<const_prefix_iterator, const_prefix_iterator> equal_prefix_range(
            const CharT *prefix, size_type prefix_size) const {
        if (m_root == nullptr) {
            return std::make_pair(prefix_cend(), prefix_cend());
        }

        return equal_prefix_range_impl(*m_root, prefix, prefix_size);
    }

    iterator longest_prefix(const CharT *key, size_type key_size) {
        if (m_root == nullptr) {
            return end();
        }

        return longest_prefix_impl(*m_root, key, key_size);
    }

    const_iterator longest_prefix(const CharT *key, size_type key_size) const {
        if (m_root == nullptr) {
            return cend();
        }

        return longest_prefix_impl(*m_root, key, key_size);
    }

    /*
     * Hash policy
     */
    float max_load_factor() const { return m_max_load_factor; }

    void max_load_factor(float ml) { m_max_load_factor = ml; }

    /*
     * Burst policy
     */
    size_type burst_threshold() const { return m_burst_threshold; }

    void burst_threshold(size_type threshold) {
        const size_type min_burst_threshold = MIN_BURST_THRESHOLD;
        m_burst_threshold = std::max(min_burst_threshold, threshold);
    }

    /*
     * Observers
     */
    hasher hash_function() const { return m_hash; }

    /*
     * Other
     */
    template<class Serializer>
    void serialize(Serializer &serializer) const {
        serialize_impl(serializer);
    }

    template<class Deserializer>
    void deserialize(Deserializer &deserializer, bool hash_compatible) {
        deserialize_impl(deserializer, hash_compatible);
    }

  private:
    /**
     * Get the begin iterator by searching for the most left descendant node
     * starting at search_start_node.
     */
    template<typename Iterator>
    Iterator cbegin(const anode &search_start_node) const noexcept {
        if (search_start_node.is_hash_node()) {
            return Iterator(search_start_node.as_hash_node());
        }

        const trie_node &tnode =
                search_start_node.as_trie_node().most_left_descendant_value_trie_node();
        if (tnode.val_node() != nullptr) {
            return Iterator(tnode);
        } else {
            const anode *first_child = tnode.first_child();
            tsl_ht_assert(first_child != nullptr);

            return Iterator(first_child->as_hash_node());
        }
    }

    /**
     * Get an iterator to the node that come just after the last descendant of
     * search_start_node.
     */
    template<typename Iterator>
    Iterator cend(const anode &search_start_node) const noexcept {
        if (search_start_node.parent() == nullptr) {
            Iterator it;
            it.set_as_end_iterator();

            return it;
        }

        const trie_node *current_trie_node = search_start_node.parent();
        const anode *next_node = current_trie_node->next_child(search_start_node);

        while (next_node == nullptr && current_trie_node->parent() != nullptr) {
            const anode *current_child = current_trie_node;
            current_trie_node = current_trie_node->parent();
            next_node = current_trie_node->next_child(*current_child);
        }

        if (next_node == nullptr) {
            Iterator it;
            it.set_as_end_iterator();

            return it;
        } else {
            return cbegin<Iterator>(*next_node);
        }
    }

    prefix_iterator prefix_end() noexcept {
        prefix_iterator it;
        it.set_as_end_iterator();

        return it;
    }

    const_prefix_iterator prefix_cend() const noexcept {
        const_prefix_iterator it;
        it.set_as_end_iterator();

        return it;
    }

    size_type size_descendants(const anode &start_node) const {
        auto first = cbegin<const_iterator>(start_node);
        auto last = cend<const_iterator>(start_node);

        size_type nb_elements = 0;
        while (first != last) {
            if (first.m_read_trie_node_value) {
                nb_elements++;
                ++first;
            } else {
                nb_elements += first.m_current_hash_node->array_hash().size();
                first.skip_hash_node();
            }
        }

        return nb_elements;
    }

    template<class... ValueArgs>
    std::pair<iterator, bool> insert_impl(anode &search_start_node,
                                          const CharT *key, size_type key_size,
                                          ValueArgs &&... value_args) {
        anode *current_node = &search_start_node;

        for (size_type ikey = 0; ikey < key_size; ikey++) {
            if (current_node->is_trie_node()) {
                trie_node &tnode = current_node->as_trie_node();

                if (tnode.child(key[ikey]) != nullptr) {
                    current_node = tnode.child(key[ikey]).get();
                } else {
                    auto hnode = make_unique<hash_node>(m_hash, m_max_load_factor);
                    auto insert_it = hnode->array_hash().emplace_ks(
                            key + ikey + 1, key_size - ikey - 1,
                            std::forward<ValueArgs>(value_args)...);

                    tnode.set_child(key[ikey], std::move(hnode));
                    m_nb_elements++;

                    return std::make_pair(
                            iterator(tnode.child(key[ikey])->as_hash_node(), insert_it.first),
                            true);
                }
            } else {
                return insert_in_hash_node(current_node->as_hash_node(), key + ikey,
                                           key_size - ikey,
                                           std::forward<ValueArgs>(value_args)...);
            }
        }

        if (current_node->is_trie_node()) {
            trie_node &tnode = current_node->as_trie_node();
            if (tnode.val_node() != nullptr) {
                return std::make_pair(iterator(tnode), false);
            } else {
                tnode.val_node() =
                        make_unique<value_node>(std::forward<ValueArgs>(value_args)...);
                m_nb_elements++;

                return std::make_pair(iterator(tnode), true);
            }
        } else {
            return insert_in_hash_node(current_node->as_hash_node(), "", 0,
                                       std::forward<ValueArgs>(value_args)...);
        }
    }

    template<class... ValueArgs>
    std::pair<iterator, bool> insert_in_hash_node(hash_node &hnode,
                                                  const CharT *key,
                                                  size_type key_size,
                                                  ValueArgs &&... value_args) {
        if (need_burst(hnode)) {
            std::unique_ptr<trie_node> new_node = burst(hnode);
            if (hnode.parent() == nullptr) {
                tsl_ht_assert(m_root.get() == &hnode);

                m_root = std::move(new_node);
                return insert_impl(*m_root, key, key_size,
                                   std::forward<ValueArgs>(value_args)...);
            } else {
                trie_node *parent = hnode.parent();
                const CharT child_of_char = hnode.child_of_char();

                parent->set_child(child_of_char, std::move(new_node));

                return insert_impl(*parent->child(child_of_char), key, key_size,
                                   std::forward<ValueArgs>(value_args)...);
            }
        } else {
            auto it_insert = hnode.array_hash().emplace_ks(
                    key, key_size, std::forward<ValueArgs>(value_args)...);
            if (it_insert.second) {
                m_nb_elements++;
            }

            return std::make_pair(iterator(hnode, it_insert.first), it_insert.second);
        }
    }

    iterator erase(iterator pos) {
        iterator next_pos = std::next(pos);

        if (pos.m_read_trie_node_value) {
            tsl_ht_assert(pos.m_current_trie_node != nullptr &&
                          pos.m_current_trie_node->val_node() != nullptr);

            pos.m_current_trie_node->val_node().reset(nullptr);
            m_nb_elements--;

            if (pos.m_current_trie_node->empty()) {
                clear_empty_nodes(*pos.m_current_trie_node);
            }

            return next_pos;
        } else {
            tsl_ht_assert(pos.m_current_hash_node != nullptr);
            auto next_array_hash_it = pos.m_current_hash_node->array_hash().erase(
                    pos.m_array_hash_iterator);
            m_nb_elements--;

            if (next_array_hash_it != pos.m_current_hash_node->array_hash().end()) {
                // The erase on array_hash invalidated the next_pos iterator, return the
                // right one.
                return iterator(*pos.m_current_hash_node, next_array_hash_it);
            } else {
                if (pos.m_current_hash_node->array_hash().empty()) {
                    clear_empty_nodes(*pos.m_current_hash_node);
                }

                return next_pos;
            }
        }
    }

    /**
     * Clear all the empty nodes from the tree starting from empty_node (empty for
     * a hash_node means that the array hash is empty, for a trie_node it means
     * the node doesn't have any child or value_node associated to it).
     */
    void clear_empty_nodes(anode &empty_node) noexcept {
        tsl_ht_assert(!empty_node.is_trie_node() ||
                      (empty_node.as_trie_node().empty() &&
                       empty_node.as_trie_node().val_node() == nullptr));
        tsl_ht_assert(!empty_node.is_hash_node() ||
                      empty_node.as_hash_node().array_hash().empty());

        trie_node *parent = empty_node.parent();
        if (parent == nullptr) {
            tsl_ht_assert(m_root.get() == &empty_node);
            tsl_ht_assert(m_nb_elements == 0);
            m_root.reset(nullptr);
        } else if (parent->val_node() != nullptr || parent->nb_children() > 1) {
            parent->child(empty_node.child_of_char()).reset(nullptr);
        } else if (parent->parent() == nullptr) {
            tsl_ht_assert(m_root.get() == empty_node.parent());
            tsl_ht_assert(m_nb_elements == 0);
            m_root.reset(nullptr);
        } else {
            /**
             * Parent is empty if we remove its empty_node child.
             * Put empty_node as new child of the grand parent instead of parent (move
             * hnode up, and delete the parent). And recurse.
             *
             * We can't just set grand_parent->child(parent->child_of_char()) to
             * nullptr as the grand_parent may also become empty. We don't want empty
             * trie_node with no value_node in the tree.
             */
            trie_node *grand_parent = parent->parent();
            grand_parent->set_child(
                    parent->child_of_char(),
                    std::move(parent->child(empty_node.child_of_char())));

            clear_empty_nodes(empty_node);
        }
    }

    iterator find_impl(const anode &search_start_node, const CharT *key,
                       size_type key_size) {
        return mutable_iterator(static_cast<const htrie_hash *>(this)->find_impl(
                search_start_node, key, key_size));
    }

    const_iterator find_impl(const anode &search_start_node, const CharT *key,
                             size_type key_size) const {
        const anode *current_node = &search_start_node;

        for (size_type ikey = 0; ikey < key_size; ikey++) {
            if (current_node->is_trie_node()) {
                const trie_node *tnode = &current_node->as_trie_node();

                if (tnode->child(key[ikey]) == nullptr) {
                    return cend();
                } else {
                    current_node = tnode->child(key[ikey]).get();
                }
            } else {
                return find_in_hash_node(current_node->as_hash_node(), key + ikey,
                                         key_size - ikey);
            }
        }

        if (current_node->is_trie_node()) {
            const trie_node &tnode = current_node->as_trie_node();
            return (tnode.val_node() != nullptr) ? const_iterator(tnode) : cend();
        } else {
            return find_in_hash_node(current_node->as_hash_node(), "", 0);
        }
    }

    const_iterator find_in_hash_node(const hash_node &hnode, const CharT *key,
                                     size_type key_size) const {
        auto it = hnode.array_hash().find_ks(key, key_size);
        if (it != hnode.array_hash().end()) {
            return const_iterator(hnode, it);
        } else {
            return cend();
        }
    }

    iterator longest_prefix_impl(const anode &search_start_node,
                                 const CharT *value, size_type value_size) {
        return mutable_iterator(
                static_cast<const htrie_hash *>(this)->longest_prefix_impl(
                        search_start_node, value, value_size));
    }

    const_iterator longest_prefix_impl(const anode &search_start_node,
                                       const CharT *value,
                                       size_type value_size) const {
        const anode *current_node = &search_start_node;
        const_iterator longest_found_prefix = cend();

        for (size_type ivalue = 0; ivalue < value_size; ivalue++) {
            if (current_node->is_trie_node()) {
                const trie_node &tnode = current_node->as_trie_node();

                if (tnode.val_node() != nullptr) {
                    longest_found_prefix = const_iterator(tnode);
                }

                if (tnode.child(value[ivalue]) == nullptr) {
                    return longest_found_prefix;
                } else {
                    current_node = tnode.child(value[ivalue]).get();
                }
            } else {
                const hash_node &hnode = current_node->as_hash_node();

                /**
                 * Test the presence in the hash node of each substring from the
                 * remaining [ivalue, value_size) string starting from the longest.
                 * Also test the empty string.
                 */
                for (std::size_t i = ivalue; i <= value_size; i++) {
                    auto it =
                            hnode.array_hash().find_ks(value + ivalue, (value_size - i));
                    if (it != hnode.array_hash().end()) {
                        return const_iterator(hnode, it);
                    }
                }

                return longest_found_prefix;
            }
        }

        if (current_node->is_trie_node()) {
            const trie_node &tnode = current_node->as_trie_node();

            if (tnode.val_node() != nullptr) {
                longest_found_prefix = const_iterator(tnode);
            }
        } else {
            const hash_node &hnode = current_node->as_hash_node();

            auto it = hnode.array_hash().find_ks("", 0);
            if (it != hnode.array_hash().end()) {
                longest_found_prefix = const_iterator(hnode, it);
            }
        }

        return longest_found_prefix;
    }

    std::pair<prefix_iterator, prefix_iterator> equal_prefix_range_impl(
            anode &search_start_node, const CharT *prefix, size_type prefix_size) {
        auto range = static_cast<const htrie_hash *>(this)->equal_prefix_range_impl(
                search_start_node, prefix, prefix_size);
        return std::make_pair(mutable_iterator(range.first),
                              mutable_iterator(range.second));
    }

    std::pair<const_prefix_iterator, const_prefix_iterator>
    equal_prefix_range_impl(const anode &search_start_node, const CharT *prefix,
                            size_type prefix_size) const {
        const anode *current_node = &search_start_node;

        for (size_type iprefix = 0; iprefix < prefix_size; iprefix++) {
            if (current_node->is_trie_node()) {
                const trie_node *tnode = &current_node->as_trie_node();

                if (tnode->child(prefix[iprefix]) == nullptr) {
                    return std::make_pair(prefix_cend(), prefix_cend());
                } else {
                    current_node = tnode->child(prefix[iprefix]).get();
                }
            } else {
                const hash_node &hnode = current_node->as_hash_node();
                const_prefix_iterator begin(
                        hnode.parent(), &hnode, hnode.array_hash().begin(),
                        hnode.array_hash().end(), false,
                        std::basic_string<CharT>(prefix + iprefix, prefix_size - iprefix));
                begin.filter_prefix();

                const_prefix_iterator end = cend<const_prefix_iterator>(*current_node);

                return std::make_pair(begin, end);
            }
        }

        const_prefix_iterator begin = cbegin<const_prefix_iterator>(*current_node);
        const_prefix_iterator end = cend<const_prefix_iterator>(*current_node);

        return std::make_pair(begin, end);
    }

    size_type erase_prefix_hash_node(hash_node &hnode, const CharT *prefix,
                                     size_type prefix_size) {
        size_type nb_erased = 0;

        auto it = hnode.array_hash().begin();
        while (it != hnode.array_hash().end()) {
            if (it.key_size() >= prefix_size &&
                std::memcmp(prefix, it.key(), prefix_size * sizeof(CharT)) == 0) {
                it = hnode.array_hash().erase(it);
                ++nb_erased;
                --m_nb_elements;
            } else {
                ++it;
            }
        }

        return nb_erased;
    }

    /*
     * Burst
     */
    bool need_burst(hash_node &node) const {
        return node.array_hash().size() >= m_burst_threshold;
    }

    /**
     * Burst the node and use the copy constructor instead of move constructor for
     * the values. Also use this method for trivial value types like int, int*,
     * ... as it requires less book-keeping (thus faster) than the burst using
     * move constructors.
     */
    template<class U = T,
            typename std::enable_if<
                    has_value<U>::value && std::is_copy_constructible<U>::value &&
                    (!std::is_nothrow_move_constructible<U>::value ||
                     !std::is_nothrow_move_assignable<U>::value ||
                     std::is_arithmetic<U>::value ||
                     std::is_pointer<U>::value)>::type * = nullptr>
    std::unique_ptr<trie_node> burst(hash_node &node) {
        const std::array<size_type, ALPHABET_SIZE> first_char_count =
                get_first_char_count(node.array_hash().cbegin(),
                                     node.array_hash().cend());

        auto new_node = make_unique<trie_node>();
        for (auto it = node.array_hash().cbegin(); it != node.array_hash().cend();
             ++it) {
            if (it.key_size() == 0) {
                new_node->val_node() = make_unique<value_node>(it.value());
            } else {
                hash_node &hnode =
                        get_hash_node_for_char(first_char_count, *new_node, it.key()[0]);
                hnode.array_hash().insert_ks(it.key() + 1, it.key_size() - 1,
                                             it.value());
            }
        }

        tsl_ht_assert(new_node->val_node() != nullptr || !new_node->empty());
        return new_node;
    }

    /**
     * Burst the node and use the move constructor and move assign operator if
     * they don't throw.
     */
    template<class U = T, typename std::enable_if<
            has_value<U>::value &&
            std::is_nothrow_move_constructible<U>::value &&
            std::is_nothrow_move_assignable<U>::value &&
            !std::is_arithmetic<U>::value &&
            !std::is_pointer<U>::value>::type * = nullptr>
    std::unique_ptr<trie_node> burst(hash_node &node) {
        /**
         * We burst the node->array_hash() into multiple arrays hash. While doing
         * so, we move each value in the node->array_hash() into the new arrays
         * hash. After each move, we save a pointer to where the value has been
         * moved. In case of exception, we rollback these values into the original
         * node->array_hash().
         */
        std::vector<T *> moved_values_rollback;
        moved_values_rollback.reserve(node.array_hash().size());

        try {
            const std::array<size_type, ALPHABET_SIZE> first_char_count =
                    get_first_char_count(node.array_hash().cbegin(),
                                         node.array_hash().cend());

            auto new_node = make_unique<trie_node>();
            for (auto it = node.array_hash().begin(); it != node.array_hash().end();
                 ++it) {
                if (it.key_size() == 0) {
                    new_node->val_node() = make_unique<value_node>(std::move(it.value()));
                    moved_values_rollback.push_back(
                            std::addressof(new_node->val_node()->m_value));
                } else {
                    hash_node &hnode =
                            get_hash_node_for_char(first_char_count, *new_node, it.key()[0]);
                    auto it_insert = hnode.array_hash().insert_ks(
                            it.key() + 1, it.key_size() - 1, std::move(it.value()));
                    moved_values_rollback.push_back(
                            std::addressof(it_insert.first.value()));
                }
            }

            tsl_ht_assert(new_node->val_node() != nullptr || !new_node->empty());
            return new_node;
        } catch (...) {
            // Rollback the values
            auto it = node.array_hash().begin();
            for (std::size_t ivalue = 0; ivalue < moved_values_rollback.size();
                 ivalue++) {
                it.value() = std::move(*moved_values_rollback[ivalue]);

                ++it;
            }

            throw;
        }
    }

    template<class U = T,
            typename std::enable_if<!has_value<U>::value>::type * = nullptr>
    std::unique_ptr<trie_node> burst(hash_node &node) {
        const std::array<size_type, ALPHABET_SIZE> first_char_count =
                get_first_char_count(node.array_hash().begin(),
                                     node.array_hash().end());

        auto new_node = make_unique<trie_node>();
        for (auto it = node.array_hash().cbegin(); it != node.array_hash().cend();
             ++it) {
            if (it.key_size() == 0) {
                new_node->val_node() = make_unique<value_node>();
            } else {
                hash_node &hnode =
                        get_hash_node_for_char(first_char_count, *new_node, it.key()[0]);
                hnode.array_hash().insert_ks(it.key() + 1, it.key_size() - 1);
            }
        }

        tsl_ht_assert(new_node->val_node() != nullptr || !new_node->empty());
        return new_node;
    }

    std::array<size_type, ALPHABET_SIZE> get_first_char_count(
            typename array_hash_type::const_iterator begin,
            typename array_hash_type::const_iterator end) const {
        std::array<size_type, ALPHABET_SIZE> count{{}};
        for (auto it = begin; it != end; ++it) {
            if (it.key_size() == 0) {
                continue;
            }

            count[as_position(it.key()[0])]++;
        }

        return count;
    }

    hash_node &get_hash_node_for_char(
            const std::array<size_type, ALPHABET_SIZE> &first_char_count,
            trie_node &tnode, CharT for_char) {
        if (tnode.child(for_char) == nullptr) {
            const size_type nb_buckets =
                    size_type(std::ceil(float(first_char_count[as_position(for_char)] +
                                              HASH_NODE_DEFAULT_INIT_BUCKETS_COUNT / 2) /
                                        m_max_load_factor));

            tnode.set_child(for_char, make_unique<hash_node>(nb_buckets, m_hash,
                                                             m_max_load_factor));
        }

        return tnode.child(for_char)->as_hash_node();
    }

    iterator mutable_iterator(const_iterator it) noexcept {
        // end iterator or reading from a trie node value
        if (it.m_current_hash_node == nullptr || it.m_read_trie_node_value) {
            typename array_hash_type::iterator default_it;

            return iterator(const_cast<trie_node *>(it.m_current_trie_node), nullptr,
                            default_it, default_it, it.m_read_trie_node_value);
        } else {
            hash_node *hnode = const_cast<hash_node *>(it.m_current_hash_node);
            return iterator(
                    const_cast<trie_node *>(it.m_current_trie_node), hnode,
                    hnode->array_hash().mutable_iterator(it.m_array_hash_iterator),
                    hnode->array_hash().mutable_iterator(it.m_array_hash_end_iterator),
                    it.m_read_trie_node_value);
        }
    }

    prefix_iterator mutable_iterator(const_prefix_iterator it) noexcept {
        // end iterator or reading from a trie node value
        if (it.m_current_hash_node == nullptr || it.m_read_trie_node_value) {
            typename array_hash_type::iterator default_it;

            return prefix_iterator(const_cast<trie_node *>(it.m_current_trie_node),
                                   nullptr, default_it, default_it,
                                   it.m_read_trie_node_value, "");
        } else {
            hash_node *hnode = const_cast<hash_node *>(it.m_current_hash_node);
            return prefix_iterator(
                    const_cast<trie_node *>(it.m_current_trie_node), hnode,
                    hnode->array_hash().mutable_iterator(it.m_array_hash_iterator),
                    hnode->array_hash().mutable_iterator(it.m_array_hash_end_iterator),
                    it.m_read_trie_node_value, it.m_prefix_filter);
        }
    }

    template<class Serializer>
    void serialize_impl(Serializer &serializer) const {
        const slz_size_type version = SERIALIZATION_PROTOCOL_VERSION;
        serializer(version);

        const slz_size_type nb_elements = m_nb_elements;
        serializer(nb_elements);

        const float max_load_factor = m_max_load_factor;
        serializer(max_load_factor);

        const slz_size_type burst_threshold = m_burst_threshold;
        serializer(burst_threshold);

        std::basic_string<CharT> str_buffer;

        auto it = begin();
        auto last = end();

        while (it != last) {
            // Serialize trie node value
            if (it.m_read_trie_node_value) {
                const CharT node_type =
                        static_cast<typename std::underlying_type<slz_node_type>::type>(
                                slz_node_type::TRIE_NODE);
                serializer(&node_type, 1);

                it.key(str_buffer);

                const slz_size_type str_size = str_buffer.size();
                serializer(str_size);
                serializer(str_buffer.data(), str_buffer.size());
                serialize_value(serializer, it);

                ++it;
            }
                // Serialize hash node values
            else {
                const CharT node_type =
                        static_cast<typename std::underlying_type<slz_node_type>::type>(
                                slz_node_type::HASH_NODE);
                serializer(&node_type, 1);

                it.hash_node_prefix(str_buffer);

                const slz_size_type str_size = str_buffer.size();
                serializer(str_size);
                serializer(str_buffer.data(), str_buffer.size());

                const hash_node *hnode = it.m_current_hash_node;
                tsl_ht_assert(hnode != nullptr);
                hnode->array_hash().serialize(serializer);

                it.skip_hash_node();
            }
        }
    }

    template<class Serializer, class U = T,
            typename std::enable_if<!has_value<U>::value>::type * = nullptr>
    void serialize_value(Serializer & /*serializer*/,
                         const_iterator /*it*/) const {}

    template<class Serializer, class U = T,
            typename std::enable_if<has_value<U>::value>::type * = nullptr>
    void serialize_value(Serializer &serializer, const_iterator it) const {
        serializer(it.value());
    }

    template<class Deserializer>
    void deserialize_impl(Deserializer &deserializer, bool hash_compatible) {
        tsl_ht_assert(m_nb_elements == 0 &&
                      m_root == nullptr);  // Current trie must be empty

        const slz_size_type version =
                deserialize_value<slz_size_type>(deserializer);
        // For now we only have one version of the serialization protocol.
        // If it doesn't match there is a problem with the file.
        if (version != SERIALIZATION_PROTOCOL_VERSION) {
            throw std::runtime_error(
                    "Can't deserialize the htrie_map/set. The protocol version header is "
                    "invalid.");
        }

        const slz_size_type nb_elements =
                deserialize_value<slz_size_type>(deserializer);
        const float max_load_factor = deserialize_value<float>(deserializer);
        const slz_size_type burst_threshold =
                deserialize_value<slz_size_type>(deserializer);

        this->burst_threshold(numeric_cast<std::size_t>(
                burst_threshold, "Deserialized burst_threshold is too big."));
        this->max_load_factor(max_load_factor);

        std::vector<CharT> str_buffer;
        while (m_nb_elements < nb_elements) {
            CharT node_type_marker;
            deserializer(&node_type_marker, 1);

            static_assert(
                    std::is_same<
                            CharT, typename std::underlying_type<slz_node_type>::type>::value,
                    "");
            const slz_node_type node_type =
                    static_cast<slz_node_type>(node_type_marker);
            if (node_type == slz_node_type::TRIE_NODE) {
                const std::size_t str_size = numeric_cast<std::size_t>(
                        deserialize_value<slz_size_type>(deserializer),
                        "Deserialized str_size is too big.");

                str_buffer.resize(str_size);
                deserializer(str_buffer.data(), str_size);

                trie_node *current_node =
                        insert_prefix_trie_nodes(str_buffer.data(), str_size);
                deserialize_value_node(deserializer, current_node);
                m_nb_elements++;
            } else if (node_type == slz_node_type::HASH_NODE) {
                const std::size_t str_size = numeric_cast<std::size_t>(
                        deserialize_value<slz_size_type>(deserializer),
                        "Deserialized str_size is too big.");

                if (str_size == 0) {
                    tsl_ht_assert(m_nb_elements == 0 && !m_root);

                    m_root = make_unique<hash_node>(
                            array_hash_type::deserialize(deserializer, hash_compatible));
                    m_nb_elements += m_root->as_hash_node().array_hash().size();

                    tsl_ht_assert(m_nb_elements == nb_elements);
                } else {
                    str_buffer.resize(str_size);
                    deserializer(str_buffer.data(), str_size);

                    auto hnode = make_unique<hash_node>(
                            array_hash_type::deserialize(deserializer, hash_compatible));
                    m_nb_elements += hnode->array_hash().size();

                    trie_node *current_node =
                            insert_prefix_trie_nodes(str_buffer.data(), str_size - 1);
                    current_node->set_child(str_buffer[str_size - 1], std::move(hnode));
                }
            } else {
                throw std::runtime_error("Unknown deserialized node type.");
            }
        }

        tsl_ht_assert(m_nb_elements == nb_elements);
    }

    trie_node *insert_prefix_trie_nodes(const CharT *prefix,
                                        std::size_t prefix_size) {
        if (m_root == nullptr) {
            m_root = make_unique<trie_node>();
        }

        trie_node *current_node = &m_root->as_trie_node();
        for (std::size_t iprefix = 0; iprefix < prefix_size; iprefix++) {
            if (current_node->child(prefix[iprefix]) == nullptr) {
                current_node->set_child(prefix[iprefix], make_unique<trie_node>());
            }

            current_node = &current_node->child(prefix[iprefix])->as_trie_node();
        }

        return current_node;
    }

    template<class Deserializer, class U = T,
            typename std::enable_if<!has_value<U>::value>::type * = nullptr>
    void deserialize_value_node(Deserializer & /*deserializer*/,
                                trie_node *current_node) {
        tsl_ht_assert(!current_node->val_node());
        current_node->val_node() = make_unique<value_node>();
    }

    template<class Deserializer, class U = T,
            typename std::enable_if<has_value<U>::value>::type * = nullptr>
    void deserialize_value_node(Deserializer &deserializer,
                                trie_node *current_node) {
        tsl_ht_assert(!current_node->val_node());
        current_node->val_node() =
                make_unique<value_node>(deserialize_value<T>(deserializer));
    }

    template<class U, class Deserializer>
    static U deserialize_value(Deserializer &deserializer) {
        // MSVC < 2017 is not conformant, circumvent the problem by removing the
        // template keyword
#if defined(_MSC_VER) && _MSC_VER < 1910
        return deserializer.Deserializer::operator()<U>();
#else
        return deserializer.Deserializer::template operator()<U>();
#endif
    }

    // Same as std::make_unique for non-array types which is only available in
    // C++14 (we need to support C++11).
    template<typename U, typename... Args>
    static std::unique_ptr<U> make_unique(Args &&... args) {
        return std::unique_ptr<U>(new U(std::forward<Args>(args)...));
    }

  public:
    static constexpr float HASH_NODE_DEFAULT_MAX_LOAD_FACTOR = 8.0f;
    static const size_type DEFAULT_BURST_THRESHOLD = 16384;

  private:
    /**
     * Fixed size type used to represent size_type values on serialization. Need
     * to be big enough to represent a std::size_t on 32 and 64 bits platforms,
     * and must be the same size on both platforms.
     */
    using slz_size_type = std::uint64_t;
    enum class slz_node_type : CharT {
        TRIE_NODE = 0, HASH_NODE = 1
    };

    /**
     * Protocol version currenlty used for serialization.
     */
    static const slz_size_type SERIALIZATION_PROTOCOL_VERSION = 1;

    static const size_type HASH_NODE_DEFAULT_INIT_BUCKETS_COUNT = 32;
    static const size_type MIN_BURST_THRESHOLD = 4;

    std::unique_ptr<anode> m_root;
    size_type m_nb_elements;
    Hash m_hash;
    float m_max_load_factor;
    size_type m_burst_threshold;
};

}  // namespace detail_htrie_hash
}  // namespace abel

#endif  // ABEL_TRIE_HTRIE_HASH_H_
